package com.example.array.doublepointer;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 *  如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
 *
 *  示例 1：
 * 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 * 输出："apple"
 *
 *  示例 2：
 * 输入：s = "abpcplea", dictionary = ["a","b","c"]
 * 输出："a"
 */
public class Leetcode524_FindLongestWord {
    public static void main(String[] args) {
        List<String> dictionary = new ArrayList<>();
        // "ale","apple","monkey","plea"
        // "abpcplea"
        //["ale","apple","monkey","plea", "abpcplaaa","abpcllllll","abccclllpppeeaaaa"]
        String[] tmps = {"ale", "apple", "monkey", "plea"};
        String s = "abpcplea";
        tmps = new String[] {"a","b","c"};
        s = "abpcplea";

        tmps = new String[] {"ale","apple","monkey","plea", "abpcplaaa","abpcllllll","abccclllpppeeaaaa"};
        s = "abpcplea";
        dictionary.addAll(Arrays.stream(tmps).collect(Collectors.toList()));
//        dictionary.sort((s1, s2) -> {
//            int diff = s1.length() - s2.length();
//            return diff != 0 ? -diff : -s1.compareTo(s2);
//        });
//        dictionary.forEach(e -> System.out.println(e));
        System.out.println(new Solution().findLongestWord(s, dictionary));
    }

    static class Solution {
        /**
         * 首先对dictionary进行排序(先按照长度由大到小进行排序,长度相等再按照字典序进行排列)
         * 然后遍历字典里的字符串看每个字符是否都在s中能被匹配上
         * @param s
         * @param dictionary
         * @return
         */
        public String findLongestWord(String s, List<String> dictionary) {
            Collections.sort(dictionary, (s1, s2) -> {
                int diff = s1.length() - s2.length();
                return diff != 0 ? -diff : s1.compareTo(s2);
            });

            boolean flag = false;
            for (String str : dictionary) {
                int beginIndex = 0;
                for (int i = 0; i < str.length(); i++) {
                    int index = s.indexOf(str.charAt(i), beginIndex);
                    if (index == -1) {
                        flag = false;
                        break;
                    } else {
                        beginIndex = index + 1;
                        flag = true;
                    }
                }
                if (flag) return str;
            }
            return "";
        }
    }
}
